import java.util.Arrays;

/**
 * @program: data_structures_algorithms
 * @description:
 * @author lld
 * @create: 2020-10-29 18:22
 **/
public class InsertSort1 {
    public static void main(String[] args) {
        int[] array = {3, 1, 7, 4, 6, 2};
        sort2(array);
    }

//    public static void sort(int[] array) {
//        for (int i = 1; i < array.length; i++) {
//            int item = array[i];
//            int index = i - 1;
//            while (index >= 0 && array[index] > item) {
//                array[index + 1] = array[index];
//                index--;
//            }
//            array[index + 1] = item;
//            System.out.println(Arrays.toString(array));
//        }
//        System.out.println(Arrays.toString(array));
//    }
//    平均时间复杂度O(n2),最好O(n),稳定的
    public static void sort2(int[] arr){
//        从第二个数开始，判断比前面的数大，不用交换，小再交换
//        相当于每次插入到有序列表中
        for(int i=1;i<arr.length;i++){
            int cur=arr[i];
            int preIndex=i-1;
            while (preIndex>=0&&cur<arr[preIndex]){
                arr[preIndex+1]=arr[preIndex];
                preIndex--;
            }
            arr[preIndex+1]=cur;
            System.out.println(Arrays.toString(arr));

        }
        System.out.println(Arrays.toString(arr));

    }
}
//3, 1, 7, 4, 6, 2  cur=1
//1 3 7 4 6 2  p=1
//1
// 3 7 4 6 2  p=3
// 3 2 4 6 7